/**
 *  @file FindIntersection.c
 *  @desc TODO 描述该文件的功能
 *  @author WangBlue(wangjiping596@gmail.com)
 *  @date 2025-07-18 14:08
 *  @version 1.0
 */


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>   // 若后续扩展布尔函数接口，可使用

// ------------------------- 节点结构定义 -------------------------

/**
 * @brief 单链表节点结构体
 */
typedef struct node {
    int           data;   ///< 数据域
    struct node  *next;   ///< 指针域：指向下一个节点
} node, *link;            ///< link 为 node* 类型别名，书写简洁

// ------------------------- 创建节点 -------------------------

/**
 * @brief 申请并初始化一个新节点
 * @param value  节点要保存的整数值
 * @return 成功返回新节点指针；若内存分配失败返回 NULL
 */
link createNode(int value) {
    link newNode = (link)malloc(sizeof(node));  // 申请节点内存
    if (newNode == NULL) return NULL;           // 分配失败，及时返回

    newNode->data = value;                      // 赋值
    newNode->next = NULL;                       // 尾指向 NULL
    return newNode;
}

// ------------------------- 头插法 -------------------------

/**
 * @brief 头插法在 *head 处插入新节点
 * @param head   指向链表头指针的指针（允许修改头指针本身）
 * @param value  要插入的数据
 * @note  复杂度 O(1)
 */
void insertHead(link *head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;                // 内存不足直接返回

    newNode->next = *head;                      // 新节点指向原头
    *head = newNode;                            // 更新头指针
}

// ------------------------- 尾插法 -------------------------

/**
 * @brief 尾插法在链表尾部追加新节点
 * @param head   指向链表头指针的指针
 * @param value  要插入的数据
 * @note  复杂度 O(n)，若维护 tail 指针可优化为 O(1)
 */
void insertTail(link *head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;

    // 1. 链表为空：新节点即为头节点
    if (*head == NULL) {
        *head = newNode;
        return;
    }

    // 2. 链表非空：遍历到末尾
    link cur = *head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = newNode;                        // 挂到尾部
}

// ------------------------- 打印链表 -------------------------

/**
 * @brief 顺序打印链表中所有节点数据
 * @param head  链表头指针
 */
void printList(link head) {
    if (head == NULL) return;                   // 空链表直接返回

    link cur = head;
    while (cur != NULL) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
}


void findIntersection(link *l1, link *l2) {
    if (*l1 == NULL || *l2 == NULL) return;
    link pa = *l1;
    link pb = *l2;
    link preA = NULL;

    while (pa && pb) {
        if (pa->data > pb->data) {
            pb = pb->next;
        } else if (pa->data < pb->data) {
            link temp = pa;
            pa = pa->next;
            free(temp);
            if (preA == NULL) {
                *l1 = pa;
            } else {
                preA->next = pa;
            }
        } else {
            preA = pa;
            pa = pa->next;
            pb = pb->next;
        }
    }

    while (pa != NULL) {
        link temp = pa;
        pa = pa->next;
        free(temp);
    }

    if (preA != NULL) {
        preA->next = NULL; // 防止野指针
    } else {
        *l1 = NULL;
    }
}

int main() {
    // 初始化链表 head1：1 → 2 → 3
    link head1 = NULL;
    insertTail(&head1, 1);
    insertTail(&head1, 2);
    insertTail(&head1, 3);

    // 初始化链表 head2：2 → 3 → 4
    link head2 = NULL;
    insertTail(&head2, 2);
    insertTail(&head2, 3);
    insertTail(&head2, 4);

    // 就地修改 head1，仅保留交集元素（2、3）
    findIntersection(&head1, &head2);

    printList(head1);

    return 0;

}